package 掘金.我好想逃却逃不掉;

public class Main {
    // 反向dfs
    static void dfs( char[][] data, boolean[][] visited, int i,int j){
        int N = data.length, M = data[0].length;

        visited[i][j] = true;
        // 向上移动
        if (i > 0 && !visited[i - 1][j]) {
            if (data[i - 1][j] == 'D'|| data[i - 1][j] == '.') {
                dfs(data, visited, i - 1, j);
            }
        }

        // 向下移动
        if (i < N - 1 && !visited[i + 1][j]) {
            if (data[i + 1][j] == 'U'|| data[i + 1][j] == '.') {
                dfs(data, visited, i + 1, j);
            }
        }

        // 向左移动
        if (j > 0 && !visited[i][j - 1]) {
            if (data[i][ j - 1] == 'R'|| data[i][ j - 1] == '.') {
                dfs(data, visited, i, j - 1);
            }
        }

        // 向右移动
        if (j < M - 1 && !visited[i][j + 1]) {
            if (data[i][j + 1] == 'L'|| data[i][j + 1] == '.') {
                dfs(data, visited, i, j + 1);
            }
        }
        //visited[i][j]=false;

    }

    public static int solution(int N, int M, char[][] data) {
        // Edit your code here
        boolean[][] visited = new boolean[N][M];
        // 找到出口0
        for(int i=0;i<N;i++){
            for (int j = 0; j < M; j++) {
                if(data[i][j]== 'O'){
                    dfs(data, visited, i, j);
                }
            }
        }
        // 统计无法到达出口的位置
        int count = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                if (!visited[i][j]) {
                    count++;
                }
            }
        }

        return count;
    }

    public static void main(String[] args) {
        // Add your test cases here
        // [".R.O", "U.L.", ".D..", "..RD"]
        char[][] pattern = {
            {'.', 'R', '.', 'O'},
            {'U', '.', 'L', '.'},
            {'.', 'D', '.', '.'},
            {'.', '.', 'R', 'D'}
    };
    
        System.out.println(solution(4, 4, pattern));
    }
}
